{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Cost of Trip With K Highways"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #graph #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #图 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 条高速公路的最大旅行费用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一系列高速公路连接从 <code>0</code> 到 <code>n - 1</code> 的 <code>n</code> 个城市。给定一个二维整数数组 <code>highways</code>，其中 <code>highways[i] = [city1<sub>i</sub>, city2<sub>i</sub>, toll<sub>i</sub>]</code> 表示有一条高速公路连接 <code>city1<sub>i</sub></code> 和<code>city2<sub>i</sub></code>，允许一辆汽车从 <code>city1<sub>i</sub></code> 前往 <code>city2<sub>i</sub></code>，<strong>反之亦然</strong>，费用为 <code>toll<sub>i</sub></code>。</p>\n",
    "\n",
    "<p>给你一个整数 <code>k</code>，你要<strong>正好</strong>经过 <code>k</code> 条公路。你可以从任何一个城市出发，但在旅途中每个城市<strong>最多</strong>只能访问一次。</p>\n",
    "\n",
    "<p>返回<em>您旅行的最大费用。如果没有符合要求的行程，则返回 <code>-1</code>。</em></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/04/18/image-20220418173304-1.png\" style=\"height: 200px; width: 327px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], k = 3\n",
    "<strong>输出:</strong> 17\n",
    "<strong>解释:</strong>\n",
    "一个可能的路径是从 0 -&gt; 1 -&gt; 4 -&gt; 3。这次旅行的费用是 4 + 11 + 2 = 17。\n",
    "另一种可能的路径是从 4 -&gt; 1 -&gt; 2 -&gt; 3。这次旅行的费用是 11 + 3 + 3 = 17。\n",
    "可以证明，17 是任何有效行程的最大可能费用。\n",
    "注意，旅行 4 -&gt; 1 -&gt; 0 -&gt; 1 是不允许的，因为你访问了城市 1 两次。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/04/18/image-20220418173342-2.png\" style=\"height: 200px; width: 217px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 4, highways = [[0,1,3],[2,3,2]], k = 2\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释:</strong> 没有长度为 2 的有效行程，因此返回-1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 15</code></li>\n",
    "\t<li><code>1 &lt;= highways.length &lt;= 50</code></li>\n",
    "\t<li><code>highways[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= city1<sub>i</sub>, city2<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>city1<sub>i</sub> != city2<sub>i</sub></code></li>\n",
    "\t<li><code>0 &lt;= toll<sub>i</sub> &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 50</code></li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">没有重复的高速公路。</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-cost-of-trip-with-k-highways](https://leetcode.cn/problems/maximum-cost-of-trip-with-k-highways/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-cost-of-trip-with-k-highways](https://leetcode.cn/problems/maximum-cost-of-trip-with-k-highways/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]]\\n3', '4\\n[[0,1,3],[2,3,2]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        if k >= n:\n",
    "            return -1\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in highways:\n",
    "            g[a].append((b, cost))\n",
    "            g[b].append((a, cost))\n",
    "        f = [[-inf] * n for _ in range(1 << n)]\n",
    "        for i in range(n):\n",
    "            f[1 << i][i] = 0\n",
    "        ans = -1\n",
    "        for i in range(1 << n):\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    for h, cost in g[j]:\n",
    "                        if i >> h & 1:\n",
    "                            f[i][j] = max(f[i][j], f[i ^ (1 << j)][h] + cost)\n",
    "                if i.bit_count() == k + 1:\n",
    "                    ans = max(ans, f[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict,deque\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param highways:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for i in highways:\n",
    "            m1[i[0]].append((i[1], i[2]))\n",
    "            m1[i[1]].append((i[0], i[2]))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check_max(start, used):\n",
    "            if len(used) == k + 1:\n",
    "                return 0\n",
    "\n",
    "            ans = -math.inf\n",
    "            for i in m1[start]:\n",
    "                if i[0] not in used:\n",
    "                    ans = max(ans, i[1] + check_max(i[0], used.union({i[0]})))\n",
    "            return ans\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            ans1 = check_max(i, frozenset({i}))\n",
    "            ans = max(ans, ans1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maximumCost( n = 4, highways = [[0,1,3],[2,3,2]], k = 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict,deque\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param highways:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for i in highways:\n",
    "            m1[i[0]].append((i[1], i[2]))\n",
    "            m1[i[1]].append((i[0], i[2]))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check_max(start, used):\n",
    "            if len(used) == k + 1:\n",
    "                return 0\n",
    "\n",
    "            ans = -math.inf\n",
    "            for i in m1[start]:\n",
    "                if i[0] not in used:\n",
    "                    ans = max(ans, i[1] + check_max(i[0], used.union({i[0]})))\n",
    "            return ans\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            ans1 = check_max(i, frozenset({i}))\n",
    "            ans = max(ans, ans1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        graph = defaultdict(dict)\n",
    "        for a, b, c in highways:\n",
    "            graph[a][b] = c\n",
    "            graph[b][a] = c\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, explored):\n",
    "            if explored.bit_count() == k + 1:\n",
    "                return 0\n",
    "\n",
    "            ans = -inf\n",
    "            for other, v in graph[cur].items():\n",
    "                if not explored & (o := 1 << other):\n",
    "                    ans = max(ans, dfs(other, explored | o) + v)\n",
    "            return ans\n",
    "\n",
    "        return max(-1, max(dfs(i, 1 << i) for i in range(n)))\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
